Everything about Modular Arithmetic totally explained
Modular arithmetic (sometimes called
modulo arithmetic, or
clock arithmetic) is a system of
arithmetic for
integers, where numbers "wrap around" after they reach a certain value — the
modulus. Modular arithmetic was introduced by
Carl Friedrich Gauss in his book
Disquisitiones Arithmeticae, published in 1801.
A familiar use of modular arithmetic is its use in the
24-hour clock: the arithmetic of time-keeping in which the day runs from midnight to midnight and is divided into 24 hours, numbered from 0 to 23. If the time is 19:00 now — 7 o'clock in the evening — then 8 hours later it'll be 3:00. Usual addition would suggest that the later time should be 19 + 8 = 27, but this isn't the answer because clock time "wraps around" at the end of the day. Likewise, if the 24-hour clock starts at 12:00 (noon) and 21 hours elapse, then the time will be 09:00 the next day, rather than 33:00. Since the hour number starts over when it reaches 24, this is arithmetic
modulo 24. Note: The clock shown below isn't a 24-hour clock, it's the more widely used 12-hour, "modulo" 12, clock.
The congruence relation
Modular arithmetic can be handled mathematically by introducing a
congruence relation on the
integers that's compatible with the operations of the
ring of integers:
addition,
subtraction, and
multiplication. For a fixed modulus
n, it's defined as follows.
Two integers
a and
b are said to be
congruent modulo n, if their difference
a −
b is an integer
multiple of
n. If this is the case, it's expressed as:
»
The above mathematical statement is read: "
a is congruent to
b modulo n".
For example,
» of integers), for example when discussing the
characteristic of a
ring.
Remainders
The notion of modular arithmetic is related to that of the
remainder in
division. The operation of finding the remainder is sometimes referred to as the
modulo operation and we may see "2 = 14 (
mod 12)". The difference is in the use of congruency, indicated by ≡, and equality indicated by =. Equality implies specifically the "common residue", the least non-negative member of an equivalence class. When working with modular arithmetic, each equivalence class is usually represented by its common residue, for example "38 ≡ 2 (
mod 12)" which can be found using
long division. It follows that, while it's correct to say "38 ≡ 14 (
mod 12)", and "2 ≡ 14 (
mod 12)", it's incorrect to say "38 = 14 (
mod 12)" (with "=" rather than "≡").
Parentheses are sometimes dropped from the expression, for example "38 ≡ 14
mod 12" or "2 = 14
mod 12", or placed around the divisor for example "38 ≡ 14
mod (12)". Notation such as "38(
mod 12)" has also been observed, but is ambiguous without contextual clarification.
The congruence relation is sometimes expressed by using
modulo instead of
mod, like "38 ≡ 14 (
modulo 12)" in
computer science. The modulo function in various computer languages typically yield the common residue, for example the statement "y = MOD(38,12);" gives y = 2.
Applications
Modular arithmetic is referenced in
number theory,
group theory,
ring theory,
knot theory,
abstract algebra,
cryptography,
computer science,
chemistry and the
visual and
musical arts.
It is one of the foundations of number theory, touching on almost every aspect of its study, and provides key examples for group theory, ring theory and abstract algebra.
In cryptography, modular arithmetic directly underpins
public key systems such as
RSA and
Diffie-Hellman, as well as providing
finite fields which underlie
elliptic curves, and is used in a variety of
symmetric key algorithms including
AES,
IDEA, and
RC4.
In computer science, modular arithmetic is often applied in
bitwise operations and other operations involving fixed-width, cyclic
data structures. The
modulo operation, as implemented in many
programming languages and
calculators, is an application of modular arithmetic that's often used in this context.
In chemistry, the last digit of the
CAS registry number (a number which is unique for each chemical compound) is a
check digit, which is calculated by taking the last digit of the first two parts of the
CAS registry number times 1, the next digit times 2, the next digit times 3 etc., adding all these up and computing the sum modulo 10.
In the visual arts, modular arithmetic can be used to create artistic patterns based on the multiplication and addition tables modulo
n (see external link, below).
In music, arithmetic modulo 12 is used in the consideration of the system of
twelve-tone equal temperament, where
octave and
enharmonic equivalency occurs (that is, pitches in a 1∶2 or 2∶1 ratio are equivalent, and C-
sharp is considered the same as D-
flat).
The method of
casting out nines offers a quick check of decimal arithmetic computations performed by hand. It is based on modular arithmetic modulo 9, and specifically on the crucial property that 10 ≡ 1 (
mod 9).
More generally, modular arithmetic also has application in disciplines such as
law (see for example,
apportionment),
economics, (see for example,
game theory) and other areas of the
social sciences, where
proportional division and allocation of resources plays a central part of the analysis.
Some neurologists (see for example,
Oliver Sacks) theorize that so-called
autistic savants utilize an "innate" modular arithmetic to compute such complex problems as what day of the week a distant date will fall on.
Computational complexity
Since modular arithmetic has such a wide range of applications, it's important to
know how hard it's to solve a system of congruences. A linear system of congruences
can be solved in
polynomial time with a form of
Gaussian elimination, for details
see the
linear congruence theorem.
Solving a system of non-linear modular arithmetic equations is
NP-complete. For details, see for example M. R. Garey, D. S. Johnson:
Computers and Intractability, a Guide to the Theory of NP-Completeness, W. H. Freeman 1979.
Further Information
Get more info on 'Modular Arithmetic'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://modular_arithmetic.totallyexplained.com">Modular arithmetic Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
